package DataStructure.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 145. 二叉树的后序遍历 https://leetcode.cn/problems/binary-tree-postorder-traversal/
 * 题目简述：给你二叉树的根节点root，返回它节点值的后序遍历。
 * 后序遍历：左右根，即对于每一棵子树，先遍历其左子树，然后遍历其右子树，最后遍历其根节点。对于一个节点，当其右孩子被访问后就接着被访问
 */
public class PostorderTraversal {

    /**
     * 思路一：递归遍历。递归函数体：先递归访问左子树，再递归访问右子树，最后访问根节点
     */
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return result;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        result.add(root.val);
        return result;
    }

    /**
     * 思路二：非递归遍历。迭代法，指针一直向左走，经过就压入栈，指向null后若栈顶元素右孩子不为null则迭代其右子树，若为null则pop栈顶元素。
     * 并根据左右根原则pop访问元素后，若其为右孩子，则直接pop访问其父节点并重复此步骤，若其为左孩子，则继续迭代父节点的右子树。
     * 注意：在一次循环中pop多次时要检查栈是否已空
     */
    public List<Integer> postorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {//指针一直向左走，经过就压入栈
                stack.push(root);
                root = root.left;
            }
            if (stack.peek().right == null) {//若栈顶元素右孩子为null则pop栈顶元素
                root = stack.pop();
                result.add(root.val);
                while (!stack.isEmpty() && stack.peek().right == root) {//pop访问元素后，若其为右孩子，则直接pop访问其父节点，重复
                    root = stack.pop();
                    result.add(root.val);
                }
            }
            root = !stack.isEmpty() ? stack.peek().right : null;//否则迭代其右子树
        }
        return result;
    }
}
